/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class BinaryTreePruning {

	public TreeNode pruneTree(TreeNode root) {
		if (help(root))
			return null;
		return root;
	}

	/**
	 * 返回是否需要删除
	 * 
	 * @param root
	 * @return
	 */
	private boolean help(TreeNode root) {
		if (root == null) {
			return true;
		}
		if (help(root.left)) {
			root.left = null;
		}
		if (help(root.right)) {
			root.right = null;
		}
		if (root.val == 1) {
			return false;
		}
		if (root.left == null && root.right == null) {// 值为0且左右都为空，当前子树需要删除
			return true;
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(0);
		TreeNode node2 = new TreeNode(0);
		TreeNode node3 = new TreeNode(1);
		TreeNode nod4 = new TreeNode(1);
		node1.left = node2;
		node1.right = node3;
		nod4.right = node1;
		System.out.println(new BinaryTreePruning().pruneTree(nod4));
	}

}
